package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 257. 二叉树的所有路径
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 * 说明: 叶子节点是指没有子节点的节点。
 * 示例:
 * 输入:
 * 1
 * /   \
 * 2     3
 * \
 * 5
 * 输出: ["1->2->5", "1->3"]
 * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 */

public class problems_257 {

    public static void main(String[] arge) {
        TreeNode node0 = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        node6.left = node2;
        node6.right = node8;
        node2.left = node0;
        node2.right = node4;
        node4.left = node3;
        node4.right = node5;
        node8.left = node7;
        node8.right = node9;
        System.out.println(new Solution().binaryTreePaths(node6));
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        List<String> ret = new ArrayList<>();
        public List<String> binaryTreePaths(TreeNode root) {
            if(null == root) return ret;
            Stack<Integer> stack = new Stack<>();
            dfs(root, stack);
            return ret;
        }
        private void dfs(TreeNode node, Stack<Integer> stack) {
            if (null == node.left && null == node.right) {
                // 到节点
                StringBuffer str = new StringBuffer();
                for (int i = 0; i < stack.size(); i++) {
                    str.append(stack.get(i));
                    str.append("->");
                }
                str.append(node.val);
                ret.add(str.toString());
            }
            stack.push(node.val);
            if (null != node.left) dfs(node.left, stack);
            if (null != node.right) dfs(node.right, stack);
            stack.pop();
        }
    }
}
